﻿/*******************************************************************
Copyright (c) 2011 이재범

*  Permission is hereby granted, free of charge, to any person
*  obtaining a copy of this software and associated documentation
*  files (the "Software"), to deal in the Software without
*  restriction, including without limitation the rights to use,
*  copy, modify, merge, publish, distribute, sublicense, and/or sell
*  copies of the Software, and to permit persons to whom the
*  Software is furnished to do so, subject to the following
*  conditions:
* 
*  The above copyright notice and this permission notice shall be
*  included in all copies or substantial portions of the Software.
* 
*  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
*  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
*  OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
*  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
*  HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
*  WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
*  FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
*  OTHER DEALINGS IN THE SOFTWARE.
*******************************************************************/

#include "hash.h"
#include "common.h"

void find_match_between_decreasing_vector(vector<int>& first, int& first_match, vector<int>& second, int& second_match);
int convert_string_to_int(string& str);
int convert_string_vector_to_int(vector<string> &vec_str);
string get_num(string &equation, int loc);

double create_relation_matrix(string equation, double& det)
{
	// equation 이 중괄호로 감싸져 있나?

	vector<int> location_operands;
	map<int, string> location_to_operand;
	string operator_name;
	int find = 0;

	while (find < static_cast<int>(equation.length()))
	{
		if(equation[find] == '\\')
		{
			if(!Equation::is_operator(equation, find, operator_name))
			{
				location_operands.push_back(find);
				location_to_operand.insert(make_pair(find, operator_name));
			}
			find = find + operator_name.length();
		}
		else if(equation[find] == '_')
		{
			location_to_operand.insert(make_pair(find, "_" + get_num(equation, find + 1))); 
			location_operands.push_back(find);
		}
		find ++;
	}

	// int 에 위치한 피연산자의 최외곽으로 감싸는 중괄호 들의 번호를 얻는다. 
	map<int, vector<int> > operand_access_table;
	vector<int>::iterator itr_operand = location_operands.begin();

	while (itr_operand != location_operands.end())
	{
		// 피연산자의 위치를 location 에 저장한다.
		int location = *itr_operand;

		// location == 0 이 된 순간 맨 바깥쪽 까지 다 넣은 것이다.
		while (location > 0)
		{
			location = find_outer_open_parenth(location, equation);

			// 찾은 바깥쪽 중괄호 ( { 의 위치)를 넣는다. 
			operand_access_table[*itr_operand].push_back(location);
		}
		itr_operand++;
	}

	// 특정 중괄호에 무슨 연산자가 작용하는지 알아낸다
	map<int, vector<string> > parenth_operator_table;
	find = 0;

	while (find < static_cast<int>(equation.length()))
	{
		// 전체 수식이 중괄호로 감싸져 있어야 함!
		if(find != 0 && (equation[find] == '{' || equation[find] == '(') )
		{
			parenth_operator_table.insert(make_pair(find, what_operator_braket(equation, find)));
		}
		find ++;
	}

	int total_number_operand = location_operands.size();	
	int **fake_operand_relation_matrix, i = 0, j = 0;

	// fake_operand_relation_matrix 는 실제 피연산자 관계 행렬이 아니다.
	// 실제는, 같은 피연산자라면 하나로 들어가 있어야 한다.
	fake_operand_relation_matrix = new int * [total_number_operand];
	while (i < total_number_operand)
	{
		fake_operand_relation_matrix[i] = new int [total_number_operand];
		i ++;
	}

	// 행렬 초기화
	for(i = 0; i < total_number_operand; i++)
	{
		for(j = 0; j < total_number_operand; j++)
		{
			fake_operand_relation_matrix[i][j] = 0;
		}
	}

	for(i = 0; i < total_number_operand; i ++)
	{
		for(j = i; j < total_number_operand; j ++)
		{
			// 일치하는 중괄호를 찾는다. 
			int match_i, match_j;
			find_match_between_decreasing_vector(
				operand_access_table[location_operands[i]], match_i,
				operand_access_table[location_operands[j]], match_j);

			match_i --;
			match_j --;
			int temp = 0;
			for(temp = 0; temp <= match_i; temp ++)
			{
				// parenth_operator_table : 어떤 중괄호에 연산자들이 무엇이 있는지.
				// operand_access_table : 어떤 피연산자에 중괄호 들이 무엇이 있는지.
				// 즉 operand_access_table[i][temp] 는 i 번째 피연산자의 temp 번째 중괄호
				fake_operand_relation_matrix[i][j] += convert_string_vector_to_int(
					parenth_operator_table[operand_access_table[location_operands[i]][temp]]);
			}
			for(temp = match_j; temp >= 0; temp --)
			{
				fake_operand_relation_matrix[i][j] += convert_string_vector_to_int(
					parenth_operator_table[operand_access_table[location_operands[j]][temp]]);
			}

			// 대칭 행렬 이므로
			fake_operand_relation_matrix[j][i] = fake_operand_relation_matrix[i][j];
		}
	}

	// 개개의 피연산자들의 이름과 위치들을 기록한다.
	map<string, vector<int> > operand_types;
	string operand_name;

	find = 0;
	while (find < static_cast<int>(equation.length()))
	{
		if(equation[find] == '\\')
		{
			if(!Equation::is_operator(equation, find, operand_name))
			{
				// operand_name 이 존재하지 않는다면
				if(operand_types.find(operand_name) == operand_types.end())
				{
					vector<int> temp;
					temp.push_back(find);

					operand_types.insert(make_pair(operand_name, temp));
				}
				// 존재 한다면
				else
				{
					operand_types[operand_name].push_back(find);
				}
			}
			find = find + operand_name.length();
		}
		else if(equation[find] == '_')
		{
			string oper_name = "_" + get_num(equation, find + 1);
			// 피연산자가 존재하지 않는다면
			if(operand_types.find(oper_name) == operand_types.end())
			{
				vector<int> temp;
				temp.push_back(find);

				operand_types.insert(make_pair(oper_name, temp));
			}
			// 존재 한다면
			else
			{
				operand_types[oper_name].push_back(find);
			}
		}
		find ++;
	}

	// 이제 진짜 operand_relation_matrix 에 기록한다. 
	int **operand_relation_matrix;
	int total_kinds_of_operand = operand_types.size();
	operand_relation_matrix = new int* [total_kinds_of_operand];

	i = 0;
	while (i < total_kinds_of_operand)
	{
		operand_relation_matrix[i] = new int [total_kinds_of_operand];
		i ++;
	}
	for(i = 0; i < total_kinds_of_operand; i++)
	{
		for(j = 0; j < total_kinds_of_operand; j++)
		{
			operand_relation_matrix[i][j] = 0;
		}
	}

	// 이제 진짜 operand_relation_matrix 를 채운다.
	map<string, vector<int> >::iterator itr_operand_type = operand_types.begin();
	for(i = 0; i < total_number_operand; i++)
	{
		for(j = i; j < total_number_operand; j++)
		{
			int loc_i = distance(operand_types.begin(), operand_types.find(location_to_operand[location_operands[i]]));
			int loc_j = distance(operand_types.begin(), operand_types.find(location_to_operand[location_operands[j]]));

			operand_relation_matrix[loc_i][loc_j] += fake_operand_relation_matrix[i][j];
			operand_relation_matrix[loc_j][loc_i] += fake_operand_relation_matrix[i][j];
		}
	}
	for(i = 0; i < total_kinds_of_operand; i++)
	{
		for(j = i; j < total_kinds_of_operand; j++)
		{
			operand_relation_matrix[i][j] /= 10;
			operand_relation_matrix[j][i] /= 10;
		}
	}

	det = calculate_determinant(operand_relation_matrix, total_kinds_of_operand);

	for(i = 0; i < total_kinds_of_operand; i++)
	{
		delete [] operand_relation_matrix[i];
	}
	for(i = 0; i < total_number_operand; i++)
	{
		delete [] fake_operand_relation_matrix[i];
	}

	delete [] fake_operand_relation_matrix;
	delete [] operand_relation_matrix;
	return 0;
}
// 감소하는 정수 벡터에서 일치하는 것을 찾는다.
void find_match_between_decreasing_vector(vector<int>& first, int& first_match, vector<int>& second, int& second_match)
{
	int first_search = 0, second_search = 0;
	while (first_search < static_cast<int>(first.size()))
	{
		if(first[first_search] > second[second_search])
		{
			first_search ++;
			continue;
		}
		else if(first[first_search] < second[second_search])
		{
			second_search ++;
			continue;
		}
		else // 일치할 경우 
		{
			break;
		}
	}

	first_match = first_search;
	second_match = second_search;
}
int convert_string_to_int(string& str)
{
	int i = 0;
	int sum = 0;
	while ( i < static_cast<int>(str.length()))
	{
		sum = sum + static_cast<int>(str[i]);
		i ++;
	}
	return sum;
}
int convert_string_vector_to_int(vector<string> &vec_str)
{
	vector<string>::iterator itr = vec_str.begin();
	int sum = 0;
	while (itr != vec_str.end())
	{
		sum = sum + convert_string_to_int(*itr);
		itr ++;
	}

	return sum;
}
string get_num(string &equation, int loc)
{
	int len = 0;
	while (true)
	{
		if(is_digit(equation[loc + len]))
			len ++;

		else
			break;
	}
	return equation.substr(loc, len);
}